package 图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode417 {
	
	 int dirs [][] = {{0,1},{0,-1},{1,0},{-1,0}};
	 	
	    List<List<Integer>> solution(int heights[][]){
		List<List<Integer>> ans = new ArrayList<>();
		int row = heights.length;
		int col = heights[0].length;
		int pArr[][] = new int [row][col]; // 记录 太平洋
		int oArr[][] = new int [row][col];// 记录 大西洋

		for(int i = 0;i < row ;i++) {
			dfs(heights,pArr,i,0);
			dfs(heights,oArr,i,col - 1);
		}
		for(int i = 0;i < col ;i++) {
			dfs(heights,pArr,0,i);
			dfs(heights,oArr,row - 1,i);
		}
		for(int  i = 0;i < row ;i++) {
			for(int j = 0;j < col ;j++) {
				if(oArr[i][j] == 1 && pArr[i][j] == 1)

					ans.add(Arrays.asList(i,j));
			}
		}
//		System.out.println();
		/**
		 * 有错误  
		 * 
		 	1 1 
			1 1 
			
			0 1 
			1 1 
		 */
		for(int arr []: pArr) {
			for(int i : arr)
				System.out.print(i + " ");
			System.out.println();
		}
		for(int arr []: oArr) {
			for(int i : arr)
				System.out.print(i + " ");
			System.out.println();
		}
		return ans;
	}
	    /**
	     * 就真离谱  呗
	     * 真纠错 还得是 debug 用肉眼 看 是 真尼玛 离谱 
	     * 为啥 会错  对比一下 之前的  这里的 代码 在这个 地方的 区别   就明白了 
	     * 因为 x y 作为  整个dfs 中的 全局   变量 多次 使用 
	     * 到这里  就已经错了
	     */ 
	 void dfs(int heights[][],int record[][],int x,int y) {
		//basecase 
		  record[x][y] = 1;
		 int temp = heights[x][y];
		 int ny = 0;
		 int nx = 0;
		 for(int i = 0;i < 4 ;i++) {
			  nx = x+ dirs[i][0];
			  ny = y + dirs[i][1];
			 // flag[x][y] == true 代表 已经 走过 这就 跳过 
			 if(ny >= heights[0].length || nx >= heights.length || nx < 0 || ny < 0 || record[nx][ny] == 1  || heights[nx][ny] < temp) {
				 continue;
			 }
			 dfs(heights,record,nx,ny);
		 }
		
	}
	
	 public static void main(String []args) {
		 int h[][] = {{2,1},{1,2}};
		 leetcode417 so = new leetcode417();
		 System.out.println(so.solution(h));
		
	 }
}
